BZOJ 3894 文理分科

Description

文理分科是一件很纠结的事情!(虽然看到这个题目的人肯定都没有纠
结过)
小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行
描述,每个格子代表一个同学的座位。每位同学必须从文科和理科中选择
一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式
得到:
1.如果第i行第秒J的同学选择了文科,则他将获得art[i][j]的满意值,如
果选择理科,将得到science[i][j]的满意值。
2.如果第i行第J列的同学选择了文科,并且他相邻(两个格子相邻当且
仅当它们拥有一条相同的边)的同学全部选择了文科,则他会更开
心,所以会增加same_art[i][j]的满意值。
3.如果第i行第j列的同学选择了理科,并且他相邻的同学全部选择了理
科,则增加same_science[i]j[]的满意值。
小P想知道,大家应该如何选择,才能使所有人的满意值之和最大。请
告诉他这个最大值。

Input

第一行为两个正整数:n,m
接下来n术m个整数,表示art[i][j];
接下来n术m个整数.表示science[i][j];
接下来n术m个整数,表示same_art[i][j];

Output

输出为一个整数,表示最大的满意值之和

Sample Input

3 4
13 2 4 13
7 13 8 12
18 17 0 5
8 13 15 4
11 3 8 11
11 18 6 5
1 2 3 4
4 2 3 2
3 1 0 4
3 2 3 2
0 2 2 1
0 2 4 4

Sample Output

152

Hint

样例说明
1表示选择文科,0表示选择理科,方案如下:
1 0 0 1
0 1 0 0
1 0 0 0
N,M<=100,读入数据均<=500

Solution

其实我不会做了……又想了2h……
发现有一些点属性相同获利的情况可以新建一个节点
从S/T到这个节点连获利,再从这个节点连到这些需要属性相同的节点
然后最小割

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>

#define maxd 100+5
#define maxn 30000+5
#define maxm 280000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct sides{
int u,v,c;
int next;
}s[maxm];

queue<int> q;
int pos[3][maxd][maxd],h[maxn];
int art[maxd][maxd],sar[maxd][maxd],sci[maxd][maxd],ssc[maxd][maxd];
int first[maxn],cur[maxn],ind;
int n,m,S,T,ans;
int st[2][4]={{1,0,-1,0},{0,1,0,-1}};

void insert(int u,int v,int c)
{

s[ind]=(sides){u,v,c,first[u]},first[u]=ind++;
s[ind]=(sides){v,u,0,first[v]},first[v]=ind++;
}

bool bfs()
{

set(h,-1),h[T]=0;
q.push(T);
while( !q.empty() ){
int sd=q.front();q.pop();
for(int i=first[sd];i!=-1;i=s[i].next)
if( s[i^1].c>0 && h[s[i].v]==-1 ){
h[s[i].v]=h[sd]+1;
q.push(s[i].v);
}
}
return h[S]!=-1;
}

int dfs(int x,int flow)
{

if( x==T ) return flow;
int used=0;
for(int &i=cur[x];i!=-1;i=s[i].next)
if( s[i].c>0 && h[s[i].v]+1==h[x] ){
int w=dfs(s[i].v,min(s[i].c,flow-used));
s[i].c-=w,s[i^1].c+=w;
used+=w;
if( used==flow ) return flow;
}
return used;
}

void dinic()
{

while( bfs() ){
for(int i=S;i<=T;i++)
cur[i]=first[i];
ans-=dfs(S,INT_MAX);
}
}

void init()
{

for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
for(int k=0;k<=2;k++)
pos[k][i][j]=k*n*m+(i-1)*m+j;
insert(S,pos[0][i][j],art[i][j]);
insert(pos[0][i][j],T,sci[i][j]);
insert(S,pos[2][i][j],sar[i][j]);
insert(pos[1][i][j],T,ssc[i][j]);
insert(pos[2][i][j],pos[0][i][j],INT_MAX);
insert(pos[0][i][j],pos[1][i][j],INT_MAX);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k<4;k++){
int sx=i+st[0][k],sy=j+st[1][k];
if( sx>=1 && sx<=n && sy>=1 && sy<=m ){
insert(pos[0][sx][sy],pos[1][i][j],INT_MAX);
insert(pos[2][i][j],pos[0][sx][sy],INT_MAX);
}
}
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("project.in","r",stdin);
freopen("project.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
set(first,-1);
S=0,T=3*n*m+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&art[i][j]),ans+=art[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&sci[i][j]),ans+=sci[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&sar[i][j]),ans+=sar[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&ssc[i][j]),ans+=ssc[i][j];
init();
dinic();
printf("%d",ans);
return 0;
}